package treeStudy;

public class LowestCommonAncestor {

    //学会声明一个全局变量接受结果。
    private TreeNode ans;
    /**
     * LeetCode T236 二叉树的最近公共祖先
     *
     * @param args
     */
    public static void main(String[] args) {

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
        if (root == null){
            return false;
        }
        boolean left = dfs(root.left, p, q);
        boolean right = dfs(root.right, p, q);

        if ((left && right) || ((root == p && (left || right)) || (root == q && (left || right)))){
            ans = root;
        }
        return (root == p || root == q) || left || right;
    }


}
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}
